struct RangeTree{ // 区间集合

using key_t = pair<int, int>;
using value_t = int;

///pbds不支持范围erase操作
std::map<key_t, value_t> shu;

RangeTree():shu(){init();}

void init(){
    shu.clear();
    /// 插入哨兵
    shu.insert({{ninf(), ninf()}, value_zero()});
    shu.insert({{inf(), inf()}, value_zero()});
}

static int inf(){
    static const int INF = 0x7F7FFFFF;
    return INF;
}

static int ninf(){return -inf();}

static value_t value_zero(){
    static const value_t VALUE_ZERO = 0;
    return VALUE_ZERO;
}

/// 插入区间[a, b]，如有必要会有合并操作
void insert(int a, int b, const value_t & v = value_zero()){
    assert(not shu.empty() and ninf() < a and a <= b and b < inf());

    key_t toInsert;
    

    /// 找到a前面一个
    auto sit = shu.lower_bound({a, inf()});
    assert(sit != shu.begin() and sit != shu.end() and sit->first.first > a);
    --sit;

    decltype(sit) toDelBegin, toDelEnd;

    if(sit->first.second + 1 >= a){
        toInsert.first = sit->first.first;
        toDelBegin = sit;
    }else{
        toInsert.first = a;
        toDelBegin = ++sit;
    }

    auto eit = shu.lower_bound({b, inf()});
    assert(eit != shu.begin() and eit != shu.end() and eit->first.first > b);

    if(eit->first.first == b + 1){
        toInsert.second = eit->first.second;
        toDelEnd = ++eit;
    }else{
        toDelEnd = eit;
        --eit;
        toInsert.second = max(eit->first.second, b);
    }

    if(toDelBegin != toDelEnd) {
        shu.erase(toDelBegin, toDelEnd);
    }
    shu.insert({toInsert, v});
    return;
}

/// 查找k所在的区间，如果k落在区间里，返回一对相等的it，否则返回前后it，因为有哨兵，一定可以返回
std::pair<std::map<key_t, value_t>::iterator, std::map<key_t, value_t>::iterator> find(int k){
    assert(not shu.empty() and ninf() < k and k < inf());
    
    /// 找到可能包含k的
    auto sit = shu.lower_bound({k, inf()});
    assert(sit != shu.begin() and sit != shu.end() and sit->first.first > k);
    --sit;    
    /// 看是否包含
    if(sit->first.first <= k and k <= sit->first.second){
        return {sit, sit};
    }
    auto eit = sit;
    ++eit;
    assert(sit->first.second < k and k < eit->first.first);
    return {sit, eit};
}

};
